package NO02;

/*
 * 【题目要求】
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 比如这样的二维数组:
 * {
 *   {1, 2, 8, 9},  
 *   {2, 4, 9, 12},  
 *   {4, 7, 10, 13},  
 *   {6, 8, 11, 15}  
 *	}
 *然后判断是否存在某一个数。
 */
public class ArraySerach {
	/*
	 * 最简单、粗暴的方式
	 */
	public static boolean ArraySearch(int[][] arr,int target){
		for(int i=0; i<arr.length; i++){
			for(int j=0; j<arr[0].length; j++){
				if(arr[i][j] == target){
					return true;
				}
			}
		}
		return false;
	}
	
	/*
	 * 
	 */
	public static boolean ArraySearch02(int[][] arr,int target){
		//健壮性
		if(arr == null || arr.length<=0 || arr[0].length<=0){
			return false;
		}
		//拿到数组的行数和列数
		int rows = arr.length;
		int cols = arr[0].length;
		//从数组的左上角元素开始比较
		int row = 0;
		int col = cols-1;
		while(col>0 && row<rows){
			if(arr[row][col] == target){
				return true;
			}else if(arr[row][col] > target){
				col--;
			}else{
				row++;
			}
		}
		return false;
	}
	
	public static void main(String[] args) {
		int[][] arr = {{1, 2, 8, 9},{2, 4, 9, 12},{4, 7, 10, 13},{6, 8, 11, 15}};
		System.out.println(ArraySearch(arr,10));
		
		System.out.println(ArraySearch02(arr,10));
	}
}
